#!/usr/bin/env python
# encoding: utf-8
'''
@author: Excelsiorly
@license: (C) Copyright 2022, All Rights Reserved.
@contact: excelsiorly@qq.com
@file: 152. 乘积最大子数组.py
@time: 2022/3/7 16:12
@desc: https://leetcode-cn.com/problems/maximum-product-subarray/
> 给你一个整数数组 nums，请你找出数组中乘积最大的非空连续子数组（该子数组中至少包含一个数字），并返回该子数组所对应的乘积。
测试用例的答案是一个32-位 整数。

子数组 是数组的连续子序列。

我们可以根据正负性进行分类讨论。
考虑当前位置如果是一个负数的话，那么我们希望以它前一个位置结尾的某个段的积也是个负数，这样就可以负负得正，并且我们希望这个积尽可能「负得更多」，
即尽可能小。如果当前位置是一个正数的话，我们更希望以它前一个位置结尾的某个段的积也是个正数，并且希望它尽可能地大。于是这里我们可以再维护一个
fmin(i)，它表示以第 ii 个元素结尾的乘积最小子数组的乘积，那么我们可以得到这样的动态规划转移方程：
            maxNum[i] = max(maxNum[i-1]*nums[i], minNum[i-1]*nums[i], nums[i])
            minNum[i] = min(maxNum[i-1]*nums[i], minNum[i-1]*nums[i], nums[i])
它代表第 i 个元素结尾的乘积最大子数组的乘积 fmax(i)，可以考虑把ai加入第 i −1 个元素结尾的乘积最大或最小的子数组的乘积中，二者加上ai
 ，三者取大，就是第 i 个元素结尾的乘积最大子数组的乘积。第 i 个元素结尾的乘积最小子数组的乘积 fmin(i)同理。

Ot(n), Os(n)
'''
class Solution:
    def maxProduct(self, nums:list) -> int:
        n = len(nums)
        # 只要保证第一个元素是nums[0]即可
        maxNum, minNum = [nums[0]]*n, [nums[0]]*n
        for i in range(1, n):
            maxNum[i] = max(maxNum[i-1]*nums[i], minNum[i-1]*nums[i], nums[i])
            minNum[i] = min(maxNum[i-1]*nums[i], minNum[i-1]*nums[i], nums[i])
        return max(maxNum)